/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 *思路：分治
 */
class MaxSubArray {
    public int maxSubArray(int[] nums) {
        return toMaxSubarray(nums,0,nums.length-1);
    }
    public int toMaxSubarray(int[] arr,int left,int right) {
        if(left>=right) {
            return arr[left];
        }
        int mid=left+((right-left)>>>1);
        int leftMax=toMaxSubarray(arr,left,mid);
        int rightMax=toMaxSubarray(arr,mid+1,right);
        int mergeMax=addMaxSubarray(arr,left,mid,right);
        return threeOfMax(leftMax,rightMax,mergeMax);
    }
    public int addMaxSubarray(int[] arr,int left,int mid,int right) {
        int leftMax=Integer.MIN_VALUE;
        int rightMax=Integer.MIN_VALUE;
        for(int i=mid,sum=0;i>=left;i--) {
            sum+=arr[i];
            if(sum>leftMax) {
                leftMax=sum;
            }
        }
        for(int i=mid+1,sum=0;i<=right;i++) {
            sum+=arr[i];
            if(sum>rightMax) {
                rightMax=sum;
            }
        }
        return leftMax+rightMax;
    }
    public int threeOfMax(int left,int right,int merge) {
        return Math.max(left,Math.max(right,merge));
    }
}